Topics: Mathematics, lectures

Speaker : Bernd Sturmfels

Topics: Mathematics, lecture

Speaker: Francis Su

Topics: Mathematics, lecture

Topics: Mathematics, lectures

Speaker : Lou Van Den Dries

Topics: Mathematics, lecture

Speaker : Philippe Flajolet Keywords: analysis of algorithms: combinatorial enumeration; analysis of algorithms;singularity analysis; limit distribution;generalizing function;symbolic method

Topics: Mathematics, lecture

Speaker : Boris Zil'ber

Topics: Mathematics, lecture

Speaker : Michael Coste

Topics: Mathematics, lecture

Speaker : Tatiana Toro

Topics: Mathematics, lecture

Speaker : Cameron Gordon

Topics: Mathematics, lecture

Speaker: Francis Su

Topics: Mathematics, lecture

Speaker : H. Edelsbrunner

Topics: Mathematics, lecture

Speaker : Markus Nebel Keywords : Analysis of algorithms; string matching problem; Boxr-Moore-Horspod algorithm; average-case analysis of algorithms. Abstract : We propose a modified version of the Boxr-Moore-Horspod algorithm which changes the order of companions such that the probability for a mismatch is maximized. Afterwards an average-case analysis for the number of companions needed by this algorithm to search for a fixed pattern verses a random pattern of size within a random text is...

Topics: Mathematics, lecture

Speaker : Michael Coste

Topics: Mathematics, lecture

Speaker : Madan Lal Mehta

Topics: Mathematics, lecture

( 1 reviews )

Topics: Mathematics, lectures

Speaker : Jan Denef

Topics: Mathematics, lecture

Speaker : Mazat

Topics: Mathematics, lecture

Speaker: Francis Su

Topics: Mathematics, lecture

Speaker: Francis Su

Topics: Mathematics, lecture

Speaker : William P. Thurston

Topics: Mathematics, lecture

Speaker : Peter Sarnack

Topics: Mathematics, lecture

Speaker : Omer Egeciogiu Keywords: Analysis of algorithms; 4-term recursions; Hankel determinants; alternating sign matrices. Abstract: There is surprising connection between a certain transform on real polynomials and a number of combinatorial structures. We discuss the elements of this connection and give conjectures on Hankel determinants and higher order recursions.

Topics: Mathematics, lecture

Speaker : Cameron Gordon

Topics: Mathematics, lecture

Speaker : Vincent Puyhaubert Keywords : Analysis of algorithms; analytic urns, stable limit law, Mellin transform, Fubini theorem, Event generating function, Convergence in distribution Abstract : We present an analytic approach to urn models. The method is the same as in Flajolet-Gabarro-Pekari wich consists in enumerating all events starting from an initial urn. A PDE is obtained for the generating function wich is solved by method of characteristics. Then the analytic study of the GF derives...

Topics: Mathematics, lecture

Speaker : Cameron Gordon

Topics: Mathematics, lecture

Speaker : Daniele Gardy Keywords: Analysis of algorithms; Boolean function representation; probability distributions on boolean functions. Abstract: We study several tree representations of boolean functions, to take into account commutativity or associativity of the boolean operators. We show how we can define related probability distributions on boonlean functions, and study some relationships between these distributions. We also consider the relation to boolean function complexity.

Topics: Mathematics, lecture

Speaker : Lou Van Den Dries

Topics: Mathematics, lecture

Speaker : Carlos Kenig

Topics: Mathematics, lecture

Speaker : Alex Wilkie

Topics: Mathematics, lecture

Speaker : Predrag Jelenkovic Keywords: Analysis of algorithms;persistent-access-caching, least-recently-used caching, least-frequently-used caching, move-to-front searching, generalized Zipf's law distributions, heavy-tailed distributions, Web caching, cache fault probability, average-case analysis, variable page sizes, long-range dependence Abstract: The most popular caching algorithms in practice are based on the Least-Recently-Used (LRU) cache replacement rule that possesses many desirable...

Topics: Mathematics, lecture

Speaker : Hosam Mahmoud Keywords : Analysis of algorithms; Poly urn; stochastic process embedding; Poissonization; Leonard pair. Abstract : We take a view of Urn models that abandons the picking of balls from an urn and considers embedded versions into a Poisson process. A connection to partial differential equations is discussed and exact and asympotic solutions are presented for diagonal cases.

Topics: Mathematics, lecture

Speaker : Michael Luby Keywords : Analysis of algorithms; LT codes; Raptor codes; fountain codes; data transportation. Abstract : The problems sending packets of information over a network, including lost packets and variable size of data, are considered with a view towards LT codes and Raptor codes.

Topics: Mathematics, lecture

Speaker : John Sullivan

Topics: Mathematics, lecture

Speaker : Bernard Gittenberger Keywords: Analysis of algorithms; systems of functions; normal limit log, combinatorial enumeration; quasi-power theorem. Abstract: When counting combinatorial objects which are defined recursively, this leads naturally to functional equations for the generating functions. We present several examples in combinatorial enumeration where the generating function satisfies a functional equation of the form $F(z,u)=Q(z,u,F(z,u))$. Various cases appear $F$ and $Q$ are...

Topics: Mathematics, lecture

Speaker : Francis Su

( 1 reviews )

Topics: Mathematics, lecture

Speaker: Francis Su

Topics: Mathematics, lecture

Speaker : Carlos Kenig

Topics: Mathematics, lecture

Speaker : Julien Fayolle

Topics: Mathematics, lecture

Speaker : Michael Drmota Keywords : Analysis of algorithms; random trees; profile height; limiting distribution; martingales; moment methods Abstract : The purpose of this talk is to surrey our results on the limiting behavior of the profile and height of various classes of random trees where the average depth is of order log n. In particular we focus on increasing trees and split trees that cover all common search trees.

Topics: Mathematics, lecture

Speaker : Zoe Chatzidakis

Topics: Mathematics, lecture

Speaker : Marcos Kiwi Keywords : Analysis of algorithms; longest common subsequence; Sankoff & Mainville conjecture; longest increasing sequence; random graphs. Abstract : We consider the length L of the longest common subsequence of two randomly, uniformly and independently chosen n. We prove conjecture of Sankoff and Mainville from the early 80's concerning the asympotic (in k) behavior limiting constant.

Topics: Mathematics, lecture

Speaker : Richard Ladner Keywords : Analysis of algorithms; Media-on-Demand, Stream Merging, Dynamic Programming, Optimal Algorithm Abstract : Steam merging is a way to take advantage of multicast and local buffer storage to dramatically reduce the bandwidth for servers delivering a media object. In this talk we present an O(n2) algorithm for optimal stream merging. In addition, we examine the special case when streams are initiated at a constant rate. In this special case there is an elegant...

Topics: Mathematics, lecture

Speaker : Bob Gomph

Topics: Mathematics, lecture

Speaker : Robert Edwards

Topics: Mathematics, lecture

Speaker : Greg Sorkin Keywords : Analysis of algorithms; average-case analysis; branching processes; Brownian motion; phase transition; scaling window; constraint satisfaction; satisfiability. Abstract : A maximum cut in a random graph below the giant component threshold can be found in linear space and linear expected time by a simple algorithm. The same algorithm solves the more general class Max 2-CSP of weighted binary 2-variable constraint satisfaction problems, which includes weighted Max...

Topics: Mathematics, lecture

Speaker : Ana Vargas

Topics: Mathematics, lecture

Speaker: Francis Su

Topics: Mathematics, lecture

Speaker: Michael FinkelbergDate: Thursday March 21, 2002 2:00 PM - 3:00 PM

Topics: Mathematics, Lectures

Speaker : Harbater

Topics: Mathematics, lecture